2907. Can
you answer these queries - 3
You are given an integer sequence a1, a2, ..., an
(|ai| ≤ 10000, 1
≤ n ≤ 50000). On this
sequence you have to apply m (m ≤ 50000) operations:
·
modify
the i-th element of the sequence
·
for
given x and y print MAX {ai
+ ai+1 + ... + aj, x ≤ i ≤ j ≤ y}
Input. The first line contains the integer n. The following line contains n integers, representing the sequence a1, a2, ..., an.
The third line contains the integer m.
The next m lines contain the
operations in following form:
·
0 x y: modify ax into y (|y| ≤ 10000).
·
1 x y: print MAX {ai + ai+1
+ ... + aj, x ≤ i ≤ j ≤ y}
Output. For each query, print an integer as the
problem required.
Sample
input
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
Sample
output
6
4
-3
SOLUTION
data structures – segment tree
Algorithm
analysis
Для решения задачи следует реализовать нетривиальное
обобщение дерева отрезков. В каждой его вершине будем хранить четыре величины:
сумму summa на этом отрезке,
максимальную сумму prefix среди всех
префиксов этого отрезка, максимальную сумму suffix
среди всех суффиксов, а также максимальную сумму max подотрезка на нём. То есть для каждого отрезка ответ будет предпосчитан
не только для него, но и для отрезков, упирающихся в его левую и правую границы.
В задаче также следует реализовать
модификацию одного элемента последовательности, одновременно с изменением
которого будут пересчитываться все четыре дополнительные величины во всех узлах
дерева отрезков, ведущих от соответствующего листа к корню.
Example
Рассмотрим массив {2, -1, 4, -2} и построим
из него дерево отрезков. В каждой вершине вычисляем значения дополнительных
величин. В листах дерева их значения равны самому элементу массива.
Вычислим
суммы элементов на отрезке [1..2]. Для этого следует совершить вызов функции
GetMax(1, 0, 3, 1, 2). Разобъем отрезок [1..2] на два фундаментальных: [1..1] и
[2..2]. Рекурсивно найдем значения величин на каждом их них (они являются
листами, поэтому все значения равны между собой и равны элементу массива),
после чего совершим сборку двух отрезков.
Algorithm
realization
Дерево отрезков храним в виде
массива t структур node длины MAX, где MAX – максимальное количество элементов,
которое может храниться в отрезке.
#define MAX 50100
struct node
{
int summa, prefix, suffix, max;
}
t[4*MAX];
На вход процедуре build построения дерева
отрезков передается массив a, номер текущей вершины дерева v и границы отрезка LeftPos
и RightPos, соответствующие вершине v.
void build (int
*a, int v, int
LeftPos, int RightPos)
{
if (LeftPos == RightPos)
{
t[v].max =
t[v].prefix = t[v].suffix = t[v].summa = a[LeftPos];
}
else
{
int Middle = (LeftPos + RightPos) / 2;
build (a, v*2,
LeftPos, Middle);
build (a, v*2+1,
Middle+1, RightPos);
t[v].summa =
t[v*2].summa + t[v*2+1].summa;
t[v].prefix =
max(t[2*v].prefix,t[2*v].summa + t[2*v+1].prefix);
t[v].suffix =
max(t[2*v+1].suffix,t[2*v].suffix + t[2*v+1].summa);
t[v].max =
max(max(t[2*v].max,t[2*v+1].max),
t[2*v].suffix
+ t[2*v+1].prefix);
}
}
Вершине v
соответствует отрезок [LeftPos; RightPos]. Функция GetMax вычисляет значения четырех
параметров (префикс, суффикс, сумма, максимальная сумма) на отрезке [Left; Right] и возвращает
структуру node, которая их содержит.
struct node GetMax(int v, int LeftPos, int RightPos, int
Left, int Right)
{
if ((Left == LeftPos) && (Right == RightPos))
return t[v];
int Middle = (LeftPos + RightPos) / 2;
if (Right <= Middle ) return
GetMax(2*v,LeftPos, Middle,Left,Right);
if (Left > Middle) return
GetMax(2*v+1,Middle+1,RightPos,Left,Right);
struct node LeftNode
= GetMax(2*v,LeftPos,Middle,Left,Middle);
struct node RightNode = GetMax(2*v+1,Middle+1,RightPos,Middle+1,Right);
struct node res;
res.prefix =
max(LeftNode.prefix,LeftNode.summa + RightNode.prefix);
res.suffix =
max(RightNode.suffix,RightNode.summa + LeftNode.suffix);
res.summa =
LeftNode.summa + RightNode.summa;
res.max =
max(max(LeftNode.max,RightNode.max),
LeftNode.suffix + RightNode.prefix);
return res;
}
Вершине v соответствует отрезок [LeftPos;
RightPos]. Функция Update изменяет значение элемента с
индексом pos на Value.
void Update(int
v, int LeftPos, int
RightPos, int pos, int
Value)
{
if (LeftPos == RightPos)
{
t[v].max =
t[v].prefix = t[v].suffix = t[v].summa = Value;
return;
}
int Middle = (LeftPos + RightPos) / 2;
if (pos <= Middle) Update(2*v, LeftPos, Middle,
pos, Value);
else Update(2*v+1, Middle+1, RightPos, pos, Value);
t[v].summa =
t[2*v].summa + t[2*v+1].summa;
t[v].max =
max(max(t[2*v].max,t[2*v+1].max),t[2*v].suffix +
t[2*v+1].prefix);
t[v].prefix =
max(t[2*v].prefix,t[2*v].summa + t[2*v+1].prefix);
t[v].suffix =
max(t[2*v+1].suffix ,t[2*v].suffix +
t[2*v+1].summa);
}
Основная часть программы. Читаем входные данные. Строим
дерево отрезков.
scanf("%d",&n);
for(i = 0; i < n; i++) scanf("%d",&mas[i]);
build(mas,1,0,n-1);
Последовательно обрабатываем m запросов.
scanf("%d",&m);
for(i = 0; i < m; i++)
{
scanf("%d",&type);
if (type)
{
scanf("%d %d",&L,&R);
res =
GetMax(1,0,n-1,L-1,R-1);
printf("%d\n",res.max);
}
else
{
scanf("%d %d",&pos,&Value);
Update(1,0,n-1,pos-1,Value);
}
}